1. Technical Field
The present invention relates in general to data processing systems, and more particularly, to an improved multi-processor data processing system. Still more particularly, the present invention relates to improved cache operation within multi-processor data processing systems.
2. Description of the Related Art
A conventional multi-processor data processing system (referred to hereinafter as an MP), typically includes a system memory, input/output (I/O) devices, multiple processing elements that each include a processor and one or more levels of high-speed cache memory, and a system bus coupling the processing elements to each other and to the system memory and I/O devices. The processors all utilize common instruction sets and communication protocols, have similar hardware architectures, and are generally provided with similar memory hierarchies.
Caches are commonly utilized to temporarily store values that might be accessed by a processor in order to speed up processing by reducing access latency as compared to loading needed values from memory. Each cache includes a cache array and a cache directory. An associated cache controller manages the transfer of data and instructions between the processor core or system memory and the cache. Typically, the cache directory also contains a series of bits utilized to track the coherency states of the data in the cache.
With multiple caches within the memory hierarchy, a coherent structure is required for valid execution results in the MP. This coherent structure provides a single view of the contents of the memory to all of the processors and other memory access devices (e.g., I/O devices). A coherent memory hierarchy is maintained through the utilization of a coherency protocol, such as the MESI protocol. In the MESI protocol, an indication of a coherency state is stored in association with each coherency granule (e.g., a cache line or sector) of one or more levels of cache memories. Each coherency granule can have one of the four MESI states, which is indicated by bits in the cache directory.
The MESI protocol allows a cache line of data to be tagged with one of four states: “M” (modified), “E” (exclusive), “S” (shared), or “I” (invalid). The Modified state indicates that a coherency granule is valid only in the cache storing the modified coherency granule and that the value of the modified coherency granule has not been written to system memory. When a coherency granule is indicated as Exclusive, then, of all caches at that level of the memory hierarchy, only that cache holds the coherency. The data in the Exclusive state is consistent with system memory, however. If a coherency granule is marked as Shared in a cache directory, the coherency granule is resident in the associated cache and in at least one other cache at the same level of the memory hierarchy, and all of the copies of the coherency granule are consistent with system memory. Finally, the Invalid state indicates that the data and address tag associated with a coherency granule are both invalid.
The state to which each coherency granule (e.g., cache line or sector) is set is dependent upon both a previous state of the data within the cache line and the type of memory access request received from a requesting device (e.g., the processor). Accordingly, maintaining memory coherency in the MP requires that the processors communicate messages across the system bus indicating their intention to read or write to memory locations. For example, when a processor desires to write data to a memory location, the processor must first inform all other processing elements of its intention to write data to the memory location and receive permission from all other processing elements to carry out the write operation. The permission messages received by the requesting processor indicate that all other cached copies of the contents of the memory location have been invalidated, thereby guaranteeing that the other processors will not access their stale local data.
In some MP systems, the cache hierarchy includes at least two levels. The level one (L1), or upper-level cache is usually a private cache associated with a particular processor core in an MP system. The processor core first looks for a data in the upper-level cache. If the requested data is not found in the upper-level cache, the processor core then access lower-level caches (e.g., level two (L2) or level three (L3) caches) for the requested data. The lowest level cache (e.g., L3) is often shared among several processor cores.
Typically, when a congruence class of one of the upper-level caches becomes full, data lines are “evicted” or written to the lower-level cache for storage. However, in any memory hierarchy, there may be several copies of the same data residing in the memory hierarchy at the same time. The policy of evicting lines to provide for more space in the upper-level cache may result in unnecessary writes to lower-level caches, which results in increased bandwidth demands.
Therefore, there is a need for a more intelligent system and method for managing a multi-level memory hierarchy to reduce unnecessary inter-cache communication.